10880번 - 내가 어디를 거쳐갔더라? 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 256 MB | 151 | 33 | 27 | 22.131% |
문제
승현이가 사는 마을은 N 개의 교차로와 M 개의 양방 통행 도로로 이루어져 있다. 각 도로는 서로 다른 두 교차로를 연결하고, 임의의 두 교차로를 1개 이상의 도로를 통해 오고 갈 수 있다. 또한, 임의의 두 교차로에 대해 서로를 직접 연결하는 도로는 최대 1개 존재한다. 이 마을은 주민 편의를 위해 각 교차로에 1부터 N까지의 번호를 붙여 놓았다.
일요일에 승현이는 자신의 집에서 출발하여 같은 마을에 사는 친구인 민수네 집에 놀러 갔다. 승현이는 이사를 온 지 얼마 되지 않았기 때문에 마을의 도로망에 대해 아는 것이 전혀 없고, 오직 자신의 집과 민수네 집만 구별할 수 있었기 때문에 오랫동안 길을 헤매다가 민수네 집에 도착했다고 한다.
승현이는 출발 이후 자신의 집이 있는 교차로에 다시 들르지 않았고, 민수네 집이 있는 교차로에 도착한 후에는 바로 민수네 집에 들어갔다는 것을 기억한다. 승현이는 민수네 집에 놀러갈 때 방문했을 가능성이 있는 교차로가 몇 개 있는지 궁금해졌다. 지적 호기심이 많은 승현이는 여기에서 한발 더 나아가, 자신의 집이 a번 교차로에 있고 민수의 집이 b번 교차로에 있었다면 방문했을 가능성이 있는 교차로가 몇 개나 있는지도 궁금해졌다.
궁금해하는 승현이를 도와줄 프로그램을 작성하자.
입력
첫 번째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 1,000)가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 승현이가 살고 있는 마을의 교차로의 수 N (2 ≤ N ≤ 200,000) 과 도로의 수 M (1 ≤ M ≤ 500,000)이 공백으로 구분되어 주어진다. 이후 M 개의 줄에는 두 개의 정수 u와 v가 공백으로 구분되어 주어지는데, 이는 마을에 u번 교차로와 v 번 교차로를 직접 연결하는 도로가 존재함을 뜻한다. 그 다음 줄에는 승현이가 궁금해한 횟수 Q (1 ≤ Q ≤ 500, 000)가 주어진다. 그 다음 Q개 줄에는 승현이의 질문에 대한 정보가 주어진다. 이 중 i (1 ≤ i ≤ Q)번째 줄에는 두 개의 정수 ai와 bi (1 ≤ ai, bi ≤ N, ai ≠ bi)가 공백을 사이에 두고 주어지는데, 이는 승현이네 집이 ai 번 교차로에 있고, 민수네 집이 bi 번 교차로에 있는 경우에 대해서 승현이의 질문에 대답해야 함을 뜻한다.
모든 테스트 케이스에서 N 의 합이 200,000을 넘지 않고, M 의 합과 Q의 합은 각각 500,000을 넘지 않는다.
출력
각 테스트 케이스에 대해 Q개의 줄을 출력한다. 이 중 i (1 ≤ i ≤ Q)번째 줄에는 i번째로 주어진 질문에 대해서, 즉 승현이네 집이 ai번 교차로에 있고, 민수네 집이 bi번 교차로에 있는 경우에 대해서 승현이가 민수네 집에 놀러가면서 방문했을 가능성이 있는 교차로의 개수를 출력한다. 서로 다른 테스트 케이스 사이에 빈 줄을 출력하면 안 된다.
예제 입력 1
1 5 5 1 2 1 3 2 4 4 5 2 5 5 1 2 1 4 2 3 2 5 3 5
예제 출력 1
2 4 3 3 5
출처
University > 전국 대학생 프로그래밍 대회 동아리 연합 > UCPC 2015 G번
Camp > Petrozavodsk Programming Camp > Winter 2023 > Day 2: GP of ainta I번
- 문제를 만든 사람: ainta
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호