压码头作为一个智障儿童，他有一些基环外向树。基环外向树可以理解为点数和边数相等的连通图.
这些基环外向树可能并不是一个连通块，所以压码头觉得有点不太珂学，于是他想要在两个不连通的基环外向树各找一个点连一条边。
压码头想让你变得更加聪颖，所以他会问你q个问题。
压码头每个问题会给出两个点的编号ui,vi，若这两点属于同一基环外向树，那么则输出这个基环外向树的最长简单路径长度，否则请告诉压码头。
在ui的基环外向树上等概率选择一点u’，在vi的基环外向树上等概率选择一点v’，连接u’,v’后，在这个新的连通图上最长简单路径的长度的期望对1004535809取模的值。