문제
영찬이는 전략 시뮬레이션 게임을 하고 있다. 처음에, 영찬이를 포함한 다른 플레이어들에게 주어진 것은 1의 공격력을 가진 기지 뿐이다. n명의 플레이어가 참가하며, 각 플레이어들은 1, 2, 3,… n의 번호로 부른다. 이 게임은 특이하게, 게임 시작 전에 두 가지 준비를 할 수 있다.
첫번째로, 게임 시작 전, 영찬이를 비롯한 플레이어들은 다른 플레이어들하고 동맹을 맺을 수 있다. 동맹을 맺은 팀은 하나의 기지처럼 취급되며, 그 공격력은 동맹을 맺기 전 팀의 공격력의 합이다. 예를 들어 {1,3,4,6}의 공격력 4 팀과 {2,5}의 공격력 2짜리 팀이 있다고 하자. 이때 1과 2가 동맹을 맺으면 이 팀은 {1,2,3,4,5,6}이 되며, 공격력 6이 된다.
두번째로, 현재의 불공정 지수를 알아볼 수 있다. 불공정 지수는, 두 팀의 공격력 차이가 c 이상인 모든 팀-순서쌍의 개수이다. 예를 들어, 팀 {1}, {2,3,4}, {5,6}이 있고, 불공정 상수가 2라면 {1}과{2,3,4}가 공격력 차이가 2 이상이기 때문에 불공정 지수는 1이 된다. 만약 불공정 상수가 1이라면 불공정 지수는 모든 순서쌍의 개수인 3이 된다. 이 상수 c는 플레이어들의 주관적 기준에 따라 달라지기 때문에, 게이머들이 물어볼 때 마다 다를 수 있다.
더 많은 n명의 플레이어들을 포용할 수 있는 게임 내부 프로그램을 개발하기 위해 전설의 프로그래머인 당신이 초빙되었다. 이 사전 준비 작업을 프로그램하라.
입력
첫 줄에 n과 q가 공백을 사이에 두고 입력된다.
n(1 ≤ n ≤ 105, 그렇다 당신은 10만명까지 플레이 할 수 있게 만들 것이다)은 플레이어의 수이고, q(1 ≤ q ≤ 2 * 105)는 사전 준비로 들어오는 지시들의 수이다.
다음 q 줄에 걸쳐서, 다음 두 가지 지시 중 하나가 들어온다.
- 1 x y
- 2 c
1 x y란 플레이어 x와 y가 동맹을 맺는다는 뜻이다.
2 c의 경우, 불공정 상수 c에 대해서 불공정 지수를 출력하라는 뜻이다.
명령들은 위 줄에서 아래 줄 순서로 시간 순서대로 입력된다.
즉, 불공정 지수를 출력할 때는 자기보다 위 줄에서 맺은 동맹들만 의미를 갖는다. (1 ≤ x, y ≤ n, 0 ≤ c ≤ 109)
출력
2 c 형태의 지시에 대해서, c의 불공정 상수로 계산한 불공정 지수를 출력하라.
예제
3 3
1 2 1
2 2
2 1
0
1
로그인해야 코드를 작성할 수 있어요.