Page not loading? Try clicking here.
Placeholder

#5929
Special judge

네트워크 1s 1024MB

Problems

1번 부터 n번까지 번호가 붙은 n개의 서버가 있고, 서버들을 연결하는 1번부터 n-1번까지 번호가 붙은 n-1개의 네트워크가 있다.

i번째 네트워크는 u[i]서버와 v[i]서버를 양방향으로 연결해주며, 모든 서버에서 다른 모든 서버로의 연결이 이어져 있음이 보장된다.

초기에 모든 n개의 서버들은 활성화되어 있고, 1번부터 m번까지의 ID를 가진 m개의 어플리케이션들이 실행중에 있다. 각각의 어플리케이션은 2개의 데이터베이스를 가지고 있다. 어플리케이션 j의 데이터베이스들은 a[j]서버와 b[j]서버에 있는데, a[j]와 b[j]가 같을 수도 있다.

어플리케이션 j가 정상적으로 작동하기 위해서는 두 데이터베이스들이 네트워크 상 연결이 되어있고, 위치한 서버들이 활성화되어 있어야한다. 좀 더 정확하게, 어플리케이션 j가 정상적으로 작동하기 위해 아래의 조건들을 충족시켜야한다:

  • 서버 a[j]와 서버 b[j] 둘 다 활성화 상태여야 한다.

  • 서버 a[j]에서 서버 b[j]로 활성화된 서버들을 통해 연결이 되어있어야 한다.

우리는 간단한 테스트를 통하여 네트워크의 견고성을 알 수 있다. 방법은 간단하다. 최소 k개의 서버를 비활성화 시켰을 때 모든 어플리케이션들의 작동이 멈춘다면 해당 네트워크의 견고성은 k이다.

네트워크의 견고성과 그 견고성이 나오기 위해 비활성화한 서버들을 출력하는 프로그램을 작성하시오.


Input

첫 번째 줄에 정수 n과 m이 주어진다. (1 \le n \le 200\ 000, 1 \le m \le 200\ 000)

다음 n-1줄 중 i번째 줄에 두 정수 u[i]와 v[i]가 주어지는데, 이는 i번째 네트워크로 연결된 두 서버를 의미한다.

다음 m줄 중 j번째 줄에 두 정수 a[j]와 b[j]가 주어지는데, 이는 j번째 어플리케이션의 데이터베이스가 저장된 두 서버를 의미한다.

  •  1 ≤ u[i], v[i] ≤ n,u[i] \ne v[i] (1 ≤ i ≤ n).

  • 1 ≤ a[j], b[j] ≤ n (1 ≤ j ≤ m)


Output

네트워크의 견고성과 그 견고성이 나오기 위해 비활성화한 서버들을 출력한다.


Subtask

# Score Condition
#14

 a[i] = b[i]

#217

 u[i] = i, v[i] = i + 1

#314

 n, m ≤ 15

#429

 n, m ≤ 2000

#536

추가 제한 없음


Example #1

9 4
1 2
2 3
2 6
3 4
4 5
4 7
6 9
7 8
6 2
5 3
4 8
5 9
2
4 2

2번 서버와 4번 서버를 비활성화 시키면 모든 어플리케이션의 작동이 중단된다.

두 개의 서버보다 더 적은 서버를 비활성화 시켜서 이를 충족하는 방법은 없기에 네트워크 견고성은 2이다.


Example #2

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

Example #3

8 3
1 2
2 3
3 4
4 5
5 6
6 7
7 8
3 5
8 5
4 4
2
4 6

Example #4

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

Source

NOI 2023 Qualification 5번
You must sign in to write code.