영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
시간 제한 1초 · 메모리 제한 512 MB
Problem
There are n cities and m flight connections between them. Your task is to add new flights so that it will be possible to travel from any city to any other city. What is the minimum number of new flights required?
Input
The first input line has two integers n and m: the number of cities and flights. The cities are numbered 1,2,…,n.
After this, there are m lines describing the flights. Each line has two integers a and b: there is a flight from city a to city b. All flights are one-way flights.
Output
First print an integer k: the required number of new flights. After this, print k lines describing the new flights. You can print any valid solution.
Constraints
- 1 ≤ n ≤ 10^5
- 1 ≤ m ≤ 2 · 10^5
- 1 ≤ a,b ≤ n
예제
예제 1
4 5 1 2 2 3 3 1 1 4 3 4
1 4 2