圣诞节将至。一年一度的难题又摆在面前——如何给妹纸送礼物。
的后宫有人，这n人之间有着复杂的关系网，相互认识的人有对。想要量化后宫之间的亲密度，于是准备给每对认识关系估一个亲密度。亲密度是个正整数，值越大说明越亲密。当然有可能有些后宫之间不直接认识，为此wyx定义了一个值，代表从第个后宫开始不断经过认识的人到，经过的亲密度最小的一对关系的最大值。不过也有可能有些后宫的朋友圈互相独立，怎么也没法通过认识的人互相到达，那么就为。
举个例子，的后宫有人，编号为。后宫和之间的亲密度为，后宫和之间的亲密度为4，后宫1和3之间的亲密度为2，后宫4由于不明原因被孤立了。那么
为了解后宫之间的亲密程度对于他选择礼物有着很重大的意义，于是他找了几个路人，测出了所有后宫之间的值。不过怀疑路人在坑爹，他想知道，是否能找到一组后宫之间的亲密度方案满足路人测出的值？由于他还要去把妹，这个问题就交给你了。