跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F2327. Xenia and Tree

  • ID: 2333
  • 传统题
  • 2000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:挑战
  • 上传者:
  • 数据结构
  • 分治
  • 树
  • 算法思想
  • 挑战
  • 难度
  • 共享题库
  • Codeforces
  • 英文题面
  • 题目来源
  • 题面语言

Xenia and Tree

题目描述

E. Xenia and Tree
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Xenia the programmer has a tree consisting of n nodes. We will consider the tree nodes indexed from 1 to n. We will also consider the first node to be initially painted red, and the other nodes − to be painted blue.

The distance between two tree nodes v and u is the number of edges in the shortest path between v and u.

Xenia needs to learn how to quickly execute queries of two types:

  1. paint a specified blue node in red;
  2. calculate which red node is the closest to the given one and print the shortest distance to the closest red node.

Your task is to write a program which will execute the described queries.

Input

The first line contains two integers n and m (2≤n≤105,1≤m≤105) − the number of nodes in the tree and the number of queries. Next n-1 lines contain the tree edges, the i-th line contains a pair of integers ai,bi (1≤ai,bi≤n,ai≠bi) − an edge of the tree.

Next m lines contain queries. Each query is specified as a pair of integers ti,vi (1≤ti≤2,1≤vi≤n). If ti=1, then as a reply to the query we need to paint a blue node vi in red. If ti=2, then we should reply to the query by printing the shortest distance from some red node to node vi.

It is guaranteed that the given graph is a tree and that all queries are correct.

Output

For each second type query print the reply in a single line.

Examples
Input
5 4
1 2
2 3
2 4
4 5
2 1
2 5
1 2
2 5
Output
0
3
2

题目来源:fps-www.educg.net-codeforce-1-2833.xml.zip;FPS 共享题包,题包内第 1945 题。保留原作者与原赛事署名。