A8885. Greedy Petya
编程题
普及/提高-
知识点
题目描述
Petya is an unexperienced programming contestant. Recently he has come across the following problem:
You are given a non-directed graph which consists of $n$ nodes and $m$ edges. Your task is to determine whether the graph contains a Hamiltonian path.
Petya wrote a quick bug-free code which he believes solves this problem. After that Petya decided to give this problem for April Fools Day contest. Unfortunately, Petya might have made a mistake, and it's quite possible that his algorithm is wrong. But this isn't a good excuse to leave the contest without submitting this problem, is it?
You are given a non-directed graph which consists of $n$ nodes and $m$ edges. Your task is to determine whether the graph contains a Hamiltonian path.
Petya wrote a quick bug-free code which he believes solves this problem. After that Petya decided to give this problem for April Fools Day contest. Unfortunately, Petya might have made a mistake, and it's quite possible that his algorithm is wrong. But this isn't a good excuse to leave the contest without submitting this problem, is it?
输入格式
The first line contains two integers $n,m$ $(1<=n<=20; 0<=m<=400)$ . Next $m$ lines contain pairs of integers $v_{i},u_{i}$ $(1<=v_{i},u_{i}<=n)$ .
输出格式
Follow the format of Petya's code output.
输入输出样例
输入 #1
2 3 1 2 2 1 1 1
输出 #1
Yes
输入 #2
3 0
输出 #2
No
输入 #3
10 20 3 10 4 6 4 9 7 5 8 8 3 10 9 7 5 2 9 2 10 6 10 4 1 1 7 2 8 4 7 2 1 8 5 4 10 2 8 5 5 2
输出 #3
No