27472번 - 깃발 꽂기 서브태스크스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 152 | 32 | 28 | 23.729% |
문제
KSA는 $N$개의 건물로 구성되어 있으며 $1, 2, \cdots, N$으로 건물 번호가 붙어 있다. 또한, 건물들 사이를 이동할 수 있는 $A$개의 지상 통로와 $B$개의 구름다리가 있다. 지상 통로는 $1, 2, \cdots, A$로, 구름다리는 $1, 2, \cdots, B$로 번호가 붙어 있다.
$i$번 지상 통로는 서로 다른 두 건물 $U_i$와 $V_i$를 양방향으로 연결한다. $(1 \le i \le A)$ 즉, $U_i$에서 $V_i$ 방향, $V_i$에서 $U_i$ 방향 모두 이동할 수 있다.
비슷하게, $i$번 구름다리는 서로 다른 두 건물 $W_i$와 $X_i$를 양방향으로 연결한다. $(1 \le i \le B)$
두 건물 사이에 지상 통로나 구름다리가 여러 개 존재할 수도 있다.
이제 아래 조건을 만족하게끔 $0$개 이상의 건물에 깃발을 꽂으려고 한다. 이때 경로의 양쪽 끝에 있는 건물도 경로에 포함된다.
- 한 개 이상의 지상 통로를 지나고, 구름다리를 지나지 않는 모든 경로에서 깃발이 꽂힌 건물의 개수는 $1$개 이상이다.
- 한 개 이상의 구름다리를 지나고, 지상 통로를 지나지 않는 모든 경로에서 깃발이 꽂힌 건물의 개수는 $1$개 이하이다.
하나의 경로는 같은 통로나 다리를 여러 번 지날 수 없다. 조건을 만족하려면 어떤 건물들에 깃발을 꽂아야 하는지 찾아보자!
입력
첫 번째 줄에 세 정수 $N$, $A$, $B$가 주어진다.
$i + 1$번째 줄에 두 정수 $U_i$, $V_i$가 주어진다. $(1 \le i \le A)$
$i + A + 1$번째 줄에 두 정수 $W_i$, $X_i$가 주어진다. $(1 \le i \le B)$
출력
첫 번째 줄에 조건을 만족하게끔 건물들에 깃발을 꽂을 수 있다면 YES, 아니라면 NO를 출력한다.
만약 꽂을 수 있다면, $0$개 이상의 정수를 출력한다. 각 정수는 깃발을 꽂을 건물들의 번호를 의미한다. 단, 같은 건물 번호를 중복해서 출력하지 않아야 한다.
깃발을 하나도 꽂지 않는 경우도 조건을 만족한다면 두 번째 줄에 아무것도 출력하지 않아도 된다.
정답이 여러 개 존재한다면 아무거나 출력해도 상관없으며, 정수들을 출력하는 순서는 상관없다.
제한
- $1 \leq N,A,B \leq 2 \times 10^5$
- $1 \le U_i, V_i \le N$; $U_i \ne V_i$ $(1 \le i \le A)$
- $1 \le W_i, X_i \le N$; $W_i \ne X_i$ $(1 \le i \le B)$
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | $A = B = 1$ |
| 2 | 25 | $N \leq 2000$ |
| 3 | 70 | 추가 제약 조건 없음 |
예제 입력 1
3 1 1 1 2 2 3
예제 출력 1
YES 1 2
예제 입력 2
4 3 3 1 2 2 3 3 4 1 2 2 3 3 4
예제 출력 2
NO
출처
High School > 한국과학영재학교 > 2023 KSA Automata Winter Contest H번
- 문제를 검수한 사람: eric00513, jk410, kiwiyou
- 문제를 만든 사람: flakepowders
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호