38494.同桌
入门
加入题单
通过率:32.14%
时间限制:1.00s
内存限制:128MB
题目描述
一个班级内有
2
�
2n 个小朋友,编号依次为
1
,
2
,
…
,
2
�
1,2,…,2n。教室里有
�
n 张桌子,每张桌子可以坐两个人。坐在同一张桌子旁边的小朋友互为同桌。一个小朋友的同桌不能是自己。
老师问每个小朋友想和谁做同桌,
�
i 号小朋友的回答是想和
�
�
p
i
号小朋友做同桌。
请你帮老师判断一下,老师能否让每个小朋友都满意?
输入格式
输入的第一行有一个正整数
�
n,表示桌子的张数。
第二行有
2
�
2n 个数
�
1
,
�
2
,
…
,
�
2
�
p
1
,p
2
,…,p
2n
,表示每个小朋友想和谁做同桌。
输出格式
如果老师可以让所有小朋友都满意,则输出 Yes,否则输出 No。
输入输出样例
输入#1
复制
3
2 1 6 5 4 3
输出#1
复制
Yes
输入#2
复制
2
1 2 4 3
输出#2
复制
No
说明/提示
【样例 1 解释】
老师可以让
1
,
2
1,2 号小朋友坐在一张桌子旁,
3
,
6
3,6 号小朋友坐在第二张桌子旁,
4
,
5
4,5 坐在第三张桌子旁。
【样例 2 解释】
1
1 号小朋友的同桌肯定不会是自己(因为每张桌子一定恰好坐
2
2 个小朋友)。
【样例 3 解释】
1
1 号小朋友想和
2
2 号小朋友做同桌,然而
2
2 号小朋友却希望和
3
3 号小朋友做同桌,所以不可能
1
,
2
1,2 号小朋友同时满意。
如果你进一步思考会发现,老师最多同时让
2
2 个小朋友满意。
对于全体数据,保证
1
≤
�
≤
5000
1≤n≤5000,
1
≤
�
�
≤
2
�
1≤p
i
≤2n。