문제

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

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

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

준혁이는 가지 배열의 가치의 합이 를 넘지 않았으면 한다.

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

입력

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

모든 입력의 첫 줄에는 실행 단계를 나타내는 정수 가 입력된다.

만약 가 이라면 첫 번째 단계를 수행해야 하고, 가 라면 두 번째 단계를 수행하면 된다.

첫 번째 단계

입력

둘째 줄에 이 주어진다.

다음 개 줄에 번 정점과 번 정점의 연결을 의미하는 트리의 간선 정보 가 주어진다.

출력

길이 의 배열 개를 배열의 순서대로 한 줄에 하나씩 출력한다. 모든 배열의 원소는 을 넘지 않는 음이 아닌 정수이고 배열 개의 가치의 합은 을 넘겨선 안된다.

두 번째 단계

입력

둘째 줄에 트리의 정점 개수이자 배열의 길이인 이 주어진다.

세번째와 네번째 줄에 첫 번째 단계에서 출력한 배열 개중 개를 임의로 골라 한 줄에 하나씩 주어진다. 이때 입력되는 배열 개가 각각 몇 번째 배열이었는지는 알 수 없다.

출력

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