시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 27 9 5 38.462%

문제

민혁이와 N-1명의 친구들이 게임을 하나씩 구매했다. 구매할 수 있는 게임은 총 M가지이고, 1번부터 M번까지 번호가 매겨져 있다. 모든 게임은 멀티플레이어 게임이고, 인터넷에 연결할 필요 없이 로컬 네트워크로 즐길 수 있다.

게임은 모여서 다같이 하면 더욱 재밌다. 민혁이는 컴퓨터를 N대 구매해 지하실에 모두 설치했고, 아직 모든 컴퓨터는 네트워크와 연결되어 있지 않다.

친구들은 자신이 구매한 게임을 민혁이네 지하실에서 하려고 한다. 민혁이는 바쁜 시간 쪼개서 모인 소중한 시간인데, 각자 알아서 게임을 하는 것은 그렇게 가치 있는 시간이라고 생각하지 않는다. 따라서, 같은 게임을 구매한 사람은 모두 같이 게임을 해야 한다.

현재 어떤 컴퓨터도 서로 연결되어 있지 않은 상태이다. 컴퓨터는 총 Q개의 랜선을 이용해서 연결하려고 한다. 랜선은 두 컴퓨터 u와 v를 연결할 수 있다. 민혁이는 랜선을 하나씩 순서대로 연결한다.

임의의 두 컴퓨터 x와 y가 같은 로컬 네트워크에 속한다는 의미는 컴퓨터 x에서 랜선을 이용해서 y로 갈 수 있을 때를 의미한다.

각 사람이 몇 번째 랜선이 연결되면 게임을 시작할 수 있는지 구해보자.

입력

첫째 줄에 사람과 컴퓨터의 수 N, 게임 종류의 수 M, 랜선의 수 Q가 주어진다.

둘째 줄에는 각 사람이 구매한 게임의 번호가 주어진다.

셋째 줄부터 Q개의 줄에는 랜선이 연결하는 두 컴퓨터의 번호가 주어진다. 같은 컴퓨터를 여러 번 연결하는 경우도 존재한다.

컴퓨터와 사람의 번호는 1부터 N까지 하나씩 매겨져 있다. 각 게임을 고른 사람의 수는 최소 1명이다.

출력

총 M개의 줄에 i번 게임을 구매한 사람은 몇 번째 랜선이 연결되면 게임을 시작할 수 있는지 출력한다. 만약, 어떤 게임을 구매한 사람이 1명이라 랜선의 연결이 필요하지 않으면 0을 출력한다. 랜선을 모두 연결해도 게임을 시작할 수 없다면 -1을 출력한다.

제한

  • 2 ≤ M ≤ N ≤ 100,000
  • 1 ≤ Q ≤ 100,000

예제 입력 1

5 2 4
1 2 2 2 1
1 2
2 3
1 5
4 5

예제 출력 1

3
4

출처