推荐题目：洛谷 P3621 [APIO2007] 风铃

推荐题目洛谷 P3621 [APIO2007] 风铃在洛谷可提交题目描述你准备给弟弟 Ike 买一件礼物但是Ike 挑选礼物的方式很特别他只喜欢那些能被他排成有序形状的东西。你准备给 Ike 买一个风铃。风铃是一种多层的装饰品一般挂在天花板上。每个风铃都包含一些由竖直线连起来的水平杆。每根杆的两头都有线连接下面或者挂着另一根水平杆或者挂着一个玩具。下面是一个风铃的例子为了满足弟弟你需要选一个满足下面两个条件的风铃所有的玩具都在同一层也就是说每个玩具到天花板之间的杆的个数是一样的或至多相差一层。对于两个相差一层的玩具左边的玩具比右边的玩具要更靠下一点。风铃可以按照下面的规则重新排列任选一根杆将杆两头的线“交换”。也就是解开一根杆左右两头的线然后将它们绑到杆的另一头。这个操作不会改变更下面的杆上线的排列顺序。正在训练信息学奥林匹克的你决定设计一个算法判断能否通过重新排列将一个给定的风铃变为 Ike 喜欢的样子。考虑上面的例子上图中的风铃满足条件1 11却不满足条件2 22——最左边的那个玩具比它右边的要高。但是我们可以通过下面的步骤把这个风铃变成一个 Ike 喜欢的第一步将杆1 11的左右两边交换这使得杆2 22和杆3 33的位置互换交换的结果如下图所示第二步也是最后一步将杆2 22的左右两边交换这使得杆4 44到了左边原来在左边的玩具到了右边交换的结果发下图所示现在的这个风铃就满足 Ike 的条件了。你的任务是给定一个风铃的描述求出最少需要多少次交换才能使这风铃满足 Ike 的条件如果可能。输入格式输入的第一行包含一个整数n nn表示风铃中有多少根杆。接下来的n nn行描述杆的连接信息。这部分的第i ii行包含两个由空格分隔的整数l i l_ili​和r i r_iri​描述杆i ii的左右两边悬挂的东西。如果挂的是一个玩具则对应的值为-1否则为挂在下面的杆的编号。输出格式输出仅包含一个整数。表示最少需要多少次交换能使风铃满足 Ike 的条件。如果不可能满足输出-1。输入输出样例 #1输入 #16 2 3 -1 4 5 6 -1 -1 -1 -1 -1 -1输出 #12说明/提示数据规模与约定对于100 % 100\%100%的数据满足1 ≤ n ≤ 10 5 1 \le n \le 10^51≤n≤105− 1 ≤ l i , r i ≤ n -1 \leq l_i, r_i \leq n−1≤li​,ri​≤nl i , r i ≠ 0 l_i, r_i \neq 0li​,ri​0。