33014번 - 3개의 배열과 트리 투 스텝

문제

이 문제는 투 스텝 문제입니다.

준혁이는 당신에게 정점 $N$개의 트리 하나를 빌려주었다. 당신은 트리를 보고 감명받아 길이 $N$의 배열 3ドル$개에 2ドルN$보다 작거나 같은 음이 아닌 정수로 값을 채워 넣어 트리를 표현하려고 한다. 각 배열은 다음과 같이 그 가치가 정해진다.

• 첫 번째 배열은 배열의 값의 합이 그 가치가 된다.
• 두 번째 배열 또한 배열의 값의 합이 그 가치가 된다.
• 세 번째 배열은 배열의 값을 모두 XOR한 결과에 $N$을 곱한 값이 그 가치가 된다.

3ドル$가지 배열의 가치의 합이 2ドルN \cdot \left \lfloor{\log_{2}N}\right \rfloor^2$를 넘어선 안 된다.

긴 시간이 지난 후, 준혁이는 트리를 다시 가져갔고, 당신은 3ドル$가지 배열 중 하나의 배열을 잃어버렸다. 당신은 잃어버리지 않은 나머지 두 배열을 보고 어떤 트리를 보고 만든 배열인지 알아내 가져간 트리를 다시 복원해야 한다.

입력

당신의 프로그램은 채점 데이터 하나당 총 두 번 실행된다. 당신은 하나의 소스코드에 두 가지 실행 과정을 모두 구현해야 한다.

모든 입력의 첫 줄에는 실행 단계를 나타내는 정수 $T$가 입력된다. $(1 \leq T \leq 2)$

만약 $T$가 1ドル$이라면 첫 번째 단계를 수행해야 하고, $T$가 2ドル$라면 두 번째 단계를 수행하면 된다.

출력

제한

첫 번째 단계

입력

둘째 줄에 $N$이 주어진다. $(4 \leq N \leq 5 \cdot 10^4)$

다음 $N-1$개 줄에 $u$번 정점과 $v$번 정점의 연결을 의미하는 트리의 간선 정보 $u, v$가 주어진다. $(1 \leq u, v \leq N)$

출력

길이 $N$의 배열 3ドル$개를 배열의 순서대로 한 줄에 하나씩 출력한다. 모든 배열의 원소는 2ドルN$을 넘지 않는 음이 아닌 정수이고 배열 3ドル$개의 가치의 합은 2ドルN \cdot \left \lfloor{\log_{2}N}\right \rfloor^2$을 넘겨선 안된다.

두 번째 단계

입력

둘째 줄에 트리의 정점 개수이자 배열의 길이인 $N$이 주어진다. $(4 \leq N \leq 5 \cdot 10^4)$

세 번째와 네 번째 줄에 첫 번째 단계에서 출력한 배열 3ドル$개중 2ドル$개가 한 줄에 하나씩 주어진다. 이때 입력되는 배열 2ドル$개가 각각 몇 번째 배열이었는지는 알 수 없다.

출력

첫 번째 단계에서 입력된 트리의 간선을 복원하여 각 간선이 연결하는 두 정점 $u$와 $v$를 $N-1$줄에 걸쳐 출력한다. 트리의 번호가 다르거나 간선 집합이 다를 경우 다른 트리이다. 간선의 순서나 $u$와 $v$의 순서는 중요하지 않다.

힌트