[백준] 9372. 상근이의 여행

사실 구글링 했다! 답이 n-1이길래 생각해본 결과

그림을 그려보니까

 

첫번째 케이스일 때 이러한 그래프가 나온다. 세 원을 다 탐색 하려면 무조건 2개 선분을 지나야한다.

두번 째 케이스

제일 아래쪽 1번부터 5번까지 돌아야하는데 그러면 그려진 선분을 다 지나야한다. 그러면 꼭지점은 5개인데 그 사이에 존재하는 선분은 1개가 더 적을 것이다. (두 점이 있어야 한 선을 만드는 것의 원리)

그래서 답은 모든 나라 N개 - 1

---

T = int(input())
for tc in range(T):
    N, M = map(int, input().split())

    for i in range(M):
        a, b = map(int, input().split())
    print(N-1)