난이도: 2 / 풀이 시간: 40분
한울이가 사는 나라에는 N개의 여행지가 있으며, 각 여행지는 1 ~ N번까지의 번호로 구분됩니다.
또한 임의의 두 여행지 사이에는 두 여행지를 연결하는 도로가 존재할 수 있습니다. 이때, 여행지가 도로로 연결되어 있다면 양방향으로 이동이 가능하다는 의미입니다.
한울이는 하나의 여행 계획을 세운 뒤에 이 여행 계획이 가능한지의 여부를 판단하고자 합니다.
예를 들어 N = 5이고, 다음과 같 이 도로의 정보가 주어졌다고 가정합시다.
* 1번 여행지 - 2번 여행지 * 1번 여행지 - 4번 여행지 * 1번 여행지 - 5번 여행지 * 2번 여행지 - 3번 여행지 * 2번 여행지 - 4번 여행지
만약 한울이의 여행 계획이 2번 -> 3번 -> 4번 -> 3번이라고 해봅시다.
이 경우 2번 -> 3번 -> 2번 -> 4번 -> 2번 -> 3번의 순서로 여행지를 방문하면, 여행 계획을 따를 수 있습니다.
여행지의 개수와 여행지 간의 연결 정보가 주어졌을 때, 한울이의 여행 계획이 가능한지의 여부를 판별하는 프로그램을 작성하세요.
입력 조건
출력 조건
입력 예시
5 4 0 1 0 1 1 1 0 1 1 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 2 3 4 3
출력 예시
YES