Graph Palindrome Queries

Each node of a tree carries a lowercase letter. Each query asks whether all characters on the unique path between two nodes (including both endpoints) can be rearranged into a palindrome.

This site has made the standard input and output explicit.

输入格式

The first line contains n q, and the second line contains n lowercase letters; then n−1 undirected edges follow, then q pairs of query nodes, 0-indexed. 1≤n,q≤100000.

输出格式

For each query, output 1 or 0.

样例 1

输入：

3 2
aba
0 1
1 2
0 2
0 1

输出：

1
0

样例 2

输入：

2 1
aa
0 1
0 1

输出：

1

样例 3

输入：

4 1
abcd
0 1
0 2
0 3
1 2

输出：

0

样例说明

Example 1: the path aba can be rearranged, while ab has two characters with odd frequency, so output 1, 0. Example 2: the two a's in aa can be paired, so output 1. Example 3: all three characters in bac have odd counts, so output 0.