놀이공원

JOI-kun에게는 여동생 IOI-chan이 있다. 지금 JOI-kun은 JOIOI 공원이라는 놀이공원에서 IOI-chan과 함께 놀고 있다.

JOIOI 공원에는 0번부터 $N-1$번까지 번호가 붙은 놀이기구 $N$개가 있다. 공원에는 길 $M$개도 있다. 각 길은 양방향으로 지날 수 있으며, 서로 다른 놀이기구 두 개를 잇는다. 길을 하나 이상 거치면 어떤 놀이기구에서든 다른 놀이기구로 갈 수 있다. JOI-kun과 IOI-chan은 공원 지도를 갖고 있어서 놀이기구끼리 어떻게 이어져 있는지 알고 있다.

각 놀이기구에는 메시지 보드가 있다. JOI-kun은 메시지 보드마다 0 또는 1 중 정수 하나만 적을 수 있다. 서로 다른 메시지 보드에는 서로 다른 값을 적을 수 있다. 한 번 적은 값은 다른 방문자가 덮어쓸 수 없다.

JOI-kun과 IOI-chan은 서로 다른 놀이기구에서 놀다가 어느 시점에 만나기로 했다. 휴대전화 같은 연락 수단이 없어서, JOI-kun은 메시지 보드로 만날 시각을 뜻하는 정수 $X$를 IOI-chan에게 전하기로 했다.

두 사람은 다음 방식으로 소통한다.

1. 먼저 JOI-kun이 모든 메시지 보드에 0 또는 1을 적는다.
2. 그다음 IOI-chan이 길을 따라 한 놀이기구에서 다른 놀이기구로 계속 이동한다. 이동하는 동안 그녀는 방문한 놀이기구마다 메시지 보드에 적힌 정수를 읽는다. 출발한 놀이기구의 메시지 보드도 포함한다.

IOI-chan은 이동 횟수를 최대한 적게 해서 정수 $X$를 알아내려고 한다.

JOI-kun이 IOI-chan에게 정수 $X$를 전할 수 있도록 프로그램 두 개를 작성하라.

• 첫 번째 프로그램은 길 정보와 정수 $X$를 받아, JOI-kun이 각 메시지 보드에 적을 0 또는 1을 정한다.
• 두 번째 프로그램은 길 정보, IOI-chan의 출발 놀이기구 $P$, 출발 놀이기구의 메시지 보드에 적힌 정수를 받는다. 길을 따라 다른 놀이기구로 이동하고, 도착한 놀이기구의 메시지 보드를 읽어서 $X$를 계산한다.

두 프로그램은 길 정보를 정확히 같은 방식으로 받는다. 특히 놀이기구 번호는 두 프로그램에서 같고, 길의 순서도 같다.

시간 제한은 2000 ms이고, 메모리 제한은 512 MB이다.

• $60 \le N \le 10000$이다.
• $1 \le M \le 20000$이다.
• $0 \le A[i] \le N-1$이다 ($0 \le i \le M-1$).
• $0 \le B[i] \le N-1$이다 ($0 \le i \le M-1$).
• $A[i] \ne B[i]$이다 ($0 \le i \le M-1$).
• $(A[i], B[i]) \ne (A[j], B[j])$이다 ($0 \le i < j \le M-1$).
• $(A[i], B[i]) \ne (B[j], A[j])$이다 ($0 \le i < j \le M-1$).
• 길을 하나 이상 거치면 어떤 놀이기구에서든 다른 놀이기구로 갈 수 있다.
• $0 \le X \le 2^{60}-1$이다.
• $0 \le P \le N-1$이다.