꼬리 달린 성원숭이

양손을 사용할 수 있는 성원숭이 N마리가 나무에 매달려 있다. 1번 성원숭이는 꼬리로 나뭇가지에 매달려 있으며, 다른 성원숭이들은 왼손과 오른손으로 다른 성원숭이를 붙잡거나 다른 성원숭이에게 붙잡혀 있을 수 있다. 붙잡는 동시에 붙잡힐 수도 있다.

각 손은 하나의 독립적인 연결이다. 두 성원숭이가 여러 손으로 이어져 있다면, 손 하나를 놓아도 남아 있는 손 연결은 계속 유지된다.

0초부터 매 초마다 지정된 성원숭이 하나가 왼손 또는 오른손을 놓는다. 손을 놓은 직후, 1번 성원숭이와 손 연결을 따라 이어져 있지 않은 성원숭이들은 즉시 땅으로 떨어진다. 각 성원숭이가 처음으로 땅에 떨어지는 시각을 구하라. 끝까지 떨어지지 않는 성원숭이도 있을 수 있다.

첫 줄에 성원숭이의 수 N과 손을 놓는 횟수 M이 주어진다.

• 1 <= N <= 200,000
• 1 <= M <= 400,000

다음 N개의 줄에는 i번 성원숭이의 왼손이 붙잡고 있는 성원숭이 번호와 오른손이 붙잡고 있는 성원숭이 번호가 순서대로 주어진다. 해당 손이 아무도 붙잡고 있지 않으면 -1이 주어진다.

다음 M개의 줄에는 손을 놓는 성원숭이의 번호와 놓는 손을 나타내는 수가 시간 순서대로 주어진다. 1은 왼손, 2는 오른손을 뜻한다. 첫 번째 줄의 사건은 0초에 일어나고, 그 다음 사건은 1초에 일어나는 식이다.

1번 성원숭이부터 N번 성원숭이까지, 각 성원숭이가 처음 땅에 떨어지는 시각을 한 줄에 하나씩 출력한다. 끝까지 떨어지지 않으면 -1을 출력한다.

어떤 손 연결이 끊어져도 다른 손 연결을 통해 1번 성원숭이와 이어져 있다면 떨어지지 않는다. 1번 성원숭이와 이어지는 마지막 연결이 끊어지는 순간, 그 연결 컴포넌트에 있던 성원숭이들이 함께 떨어진다.