시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
0.1 초 32 MB (%)
문제
N개의 노드와, 두 노드를 단방향으로 잇는 링크 M개로 구성된 네트워크가 있다. 노드 p에서 q로 “도달가능하다”는 것은 다음을 만족하는 서로 다른 노드들의 수열 $(p_1, p_2, \cdots , p_k)$가 존재한다는 것을 의미한다: *"$p_1$은 p이고, $p_k$는 q이며, 각각의 $i=1, \cdots, k-1$에 대해서 $p_i$에서 $p_{i+1}$로 가는 링크가 존재한다."* 이 네트워크에서는 어떤 노드 p에서 q로 도달가능할 수도 있고, 도달가능하지 않을 수도 있다. 단, 도달가능한 경우는 그 경로가 유일하여, p에서 q로 가는 서로 다른 경로가 2개 이상 있지 않음이 보장된다. 또한 이 네트워크에서는 "핵심노드"라는 것이 존재해야 하는데, 이 핵심노드 r에서는 다른 모든 노드로 도달가능해야 한다.
Drawing
관리자는 네트워크를 개편하기 위하여 두 가지 방법을 고려하고 있다. 첫 번째 방법은 핵심노드를 다시 정하는 것인데, 이를 위해서 각각의 노드에 대해서 그 노드로부터 도달가능한 노드들의 개수를 알고싶어 한다. 두 번째 방법은 핵심노드의 개념을 없애고 아예 모든 두 노드 p, q에 대해 p에서 q로 도달하는 경로가 정확히 1개씩 존재하도록 링크 몇 개를 추가하는 것이다. 각 노드에 대해서 그 노드로부터 도달가능한 노드들의 개수를 구하고(서브태스크A), 모든 노드들이 서로 유일한 경로를 통해 도달가능하도록 만들기 위하여 추가해야 하는 링크의 최소 개수와 그 때 필요한 링크들의 목록을 구하는 프로그램을 작성하라.(서브태스크B)
입력
표준 입력에서 다음의 입력을 읽는다. 첫 줄에는 노드의 개수를 나타내는 N(1 $\leq$ N $\leq$ 100,000), 링크의 개수를 나타내는 M(1 $\leq$ M $\leq$ 500,000), 그리고 핵심노드의 번호를 나타내는 r(1 $\leq$ r $\leq$ N)이 주어진다. 다음 M개의 줄에는 링크에 대한 정보가 주어진다. 각각의 줄에는 p에서 q로 직접 연결하는 링크가 존재한다는 뜻으로 두 정수 p와 q가 빈 칸을 사이에 두고 주어진다. 각 노드들은 1부터 N까지의 번호를 가진다.
출력
표준 출력으로 다음을 출력한다. 첫 번째 줄에 서브태스크A에 대한 답을 출력한다. N개의 정수를 빈 칸을 사이에 두고 출력하며, i번째 수는 노드 i로부터 도달가능한 노드들의 개수여야 한다. (이 때 각 노드는 자기 자신으로 도달가능하다고 친다.) 출력의 두 번째 줄에는 서브태스크B를 수행하기 위해 추가해야 하는 링크의 최소 개수 K를 출력한다. 다음 K개의 줄에는 실제로 어떤 링크를 추가해야 하는지를 출력한다. u에서 v로 연결하는 링크를 추가해야 한다면 각각의 줄에 두 정수 u와 v를 빈 칸을 사이에 두고 출력하라. 만일 여러가지 답이 가능하다면 아무 답이나 출력해도 된다.
힌트
다음 항목들에 대하여 부분점수를 받을 수 있다. - 테스트 케이스의 50%에 대해서는 N $\leq$ 10,000이다. - 서브태스크A는 전체 점수의 40%, 서브태스크B는 전체 점수의 60%이다. - 서브태스크B만 풀 경우에도, 무조건 첫 번째 줄에 N개의 정수를 출력해야 한다. (아무거나라도) #### 입력 예시 ``` 11 12 3 3 2 2 1 2 4 4 5 4 6 6 2 6 7 3 8 8 9 9 10 9 11 10 8 ``` #### 출력 예시 ``` 1 6 11 6 1 6 1 4 4 4 1 5 1 3 5 4 7 6 11 9 8 3 ```