九度Online Judge

OJ新增积分机制,如有任何问题或者建议,请发帖到九度论坛OJ意见反馈版,祝大家一切顺利!
亲,九度OJ官方微博开通了,欢迎你来粉!微博地址:weibo.com/jobdu

 题目1424-九度Online Judge,用代码记录你的成长之路!

题目1424:Crop Circle

时间限制:1 秒

内存限制:32 兆

特殊判题:

提交:258

解决:65

题目描述:

         A crop circle is a sizable pattern created by the flattening of a crop such as wheat, barley, rye, maize, or rapeseed. In this problem, all the circles are distinct and do not intersect. 

        Now Lost ( a "GaoShuaiFu" in ACM_DIY) had taken one photo of the circles. He gives some information about the circles. In the photo, n circles could be recognized and they are marked as 1,2,...n. Then for some circle C_i. Lost counts the number of circles that are "directly inside" it, here "directly inside" means Lost only consider the circles that are only inside C_i but not inside any other circles who is smaller that C_i.

        For example:

Figure 1. One Example

          Here when count the number of circles that are directly inside the blue one, we only consider the red and the pink one since the green one is inside the pink one which is smaller that the blue one. Lost counts and then tell us m tips. 

        However, Lost is evil, sometimes he may play trick on us. We want to know if  such a valid crop circles exists? 

输入:

        The first line is one integer T indicates the number of the test cases. (T <= 50)

Then for every case, the first line has two integer n and m, indicating the number of the circle and the number of circle that lost count.(1≤n≤16,0≤m≤100 )

        Then m lines, each line has two integer x and y, indicate the identifier of the circle and the number of circle that are "directly inside" it. (1≤x≤n,|y|≤1000)


输出:





样例输入:
3
6 6
1 2
2 0
3 0
4 1
5 1
6 0
6 2
1 4
2 4
6 2
1 4
2 1
样例输出:
YES
NO
YES
提示:

In case 1, the following figure is one possible solution:

来源:
第四届ACM_DIY群程序设计竞赛