Maximizing Ice Blocks on the Gym Path

In the popular Pokémon games (Red/Blue/Green/Gem), the water‐type gym was located beyond three icy areas. In each icy area there are several thin ice blocks, each of which can be stepped on at most once. Only after all ice blocks in an area have been stepped on will the staircase to the next area open.

Inspired by this, the gym leader has redesigned the challenge. The gym is now divided into n rooms that form a tree (i.e. there is exactly one simple path between any two rooms). Each room consists of two regions, labeled A and B. Each region is either a thin ice block or an obstacle. A challenger may move as follows:

• Within the same room, one may switch from one region to the other. (Note that if both regions are ice blocks, the challenger can step on both, but cannot step on the same region twice.)
• From a room to an adjacent room (rooms connected by an edge), the challenger can move only to the region with the same label as the one he is currently in.

Furthermore, if the challenger is in room u and the gym leader is in room v, then on each move the challenger is only allowed to proceed in the direction that brings him closer to room v (i.e. along the unique simple path from u to v in the tree).

The challenge begins in room u, where the challenger can choose either region, provided that region is an ice block. In every room on the path to room v, if the challenger enters using region L (where L is either A or B) and if that region is an ice block, then he obtains 1 point for that room. However, if the other region in the same room is also an ice block, he may, before leaving the room, switch to that region to collect an extra point (thereby making the total for the room 2) – in this case his departure label becomes the opposite region.

The moment the maximal number of ice blocks is stepped on (i.e. no other strategy could result in a higher count), once the challenger steps on the final ice block along the path, he is instantly teleported to battle the gym leader.

Since the gym leader revised the rules, m days have passed. Each day an event takes place. An event is either:

• A challenge where a challenger starts at room u with the gym leader in room v, and you are to compute the maximum number of ice blocks that can be stepped on along the unique simple path from u to v following the rules above. If it is impossible for the challenger to proceed (i.e. some required region is an obstacle), output -1.
• A modification where the gym leader changes the configuration of a room. For a room x, two integers are provided to update its regions: the new status for region A and region B (1 indicating an ice block and 0 indicating an obstacle).

Input must be parsed from standard input and output written to standard output.

Notation in formulas:

Let the configuration of room i be represented by $a_i$ and $b_i$, where:

[ a_i,b_i \in {0,1}. ]

The decision in a room when entering with region L is as follows:

[ \text{If } a_i \text{ denotes region A and } b_i \text{ denotes region B, then:} ]

[ \begin{array}{ll} \text{If entering with } L, \text{ and } (\text{region } L=1) & \text{you may choose not to switch and get } 1 \text{ point (exit label } L\text{)};\[6pt] \text{If } (\text{region } L=1 \text{ and } \text{region } (1-L)=1) & \text{you may switch to region } (1-L) \text{ and get } 2 \text{ points (exit label } 1-L\text{)}.\ \end{array} ]

The overall maximum is the sum over rooms along the path. For the starting room, the challenger may choose any available region and can switch if both regions are available.

inputFormat

The first line contains two integers n and m --- the number of rooms and the number of events.

The next n lines each contain two integers. The i-th of these lines contains a_i and b_i (each is 0 or 1) which represent the status of region A and region B in room i (1 means an ice block, 0 means an obstacle).

The following n-1 lines each contain two integers u and v describing an edge between rooms u and v (the rooms form a tree).

Then follow m lines, each describing an event. An event is in one of the following formats:

• 1 u v: a challenge event, where the challenger starts at room u and the gym leader is in room v.
• 2 x a b: a modification event, meaning that room x is updated so that region A becomes a and region B becomes b (each is either 0 or 1).

Note: Rooms are numbered from 1 to n.

outputFormat

For each challenge event (event type 1), output a single line containing one integer --- the maximum number of ice blocks the challenger can step on along the unique path from the starting room to the gym leader’s room, using an optimal strategy. If it is impossible to travel along the path (i.e. a required region is an obstacle), output -1.

sample

5 5
1 1
1 0
0 1
1 1
0 0
1 2
2 3
2 4
4 5
1 1 3
1 1 5
2 5 1 0
1 1 5
1 4 3

2
-1
3
2

</p>