Given a non-empty tree with root , and with weight $W_i$ assigned to each tree node $T_i$. The weight of a path from  to  is defined to be the sum of the weights of all the nodes along the path from  to any leaf node .

Now given any weighted tree, you are supposed to find all the paths with their weights equal to a given number. For example, let’s consider the tree showed in the following figure: for each node, the upper number is the node ID which is a two-digit number, and the lower number is the weight of that node. Suppose that the given number is 24, then there exists 4 different paths which have the same given weight: {10 5 2 7}, {10 4 10}, {10 3 3 6 2} and {10 3 3 6 2}, which correspond to the red edges in the figure.

Input Specification:

Each input file contains one test case. Each case starts with a line containing , the number of nodes in a tree,  (), the number of non-leaf nodes, and $0 < S < 2^{30}$, the given weight number. The next line contains positive numbers where $W_i$() corresponds to the tree node $T_i$. Then  lines follow, each in the format:

ID K ID[1] ID[2] … ID[K]

where ID is a two-digit number representing a given non-leaf node, K is the number of its children, followed by a sequence of two-digit ID‘s of its children. For the sake of simplicity, let us fix the root ID to be 00.

Output Specification:

For each test case, print all the paths with weight S in non-increasing order. Each path occupies a line with printed weights from the root to the leaf in order. All the numbers must be separated by a space with no extra space at the end of the line.

Note: sequence $\{A_1,A_2,…A_n\}$is said to be greater than sequence$\{B_1,B_2,…B_m\}$if there exists $1\leq k< \min\{n.m\}$such that$A_i=B_i$for$i=1,…,k$,and $A_{k+1}>B_{k+1}$

Sample Input:

20 9 24
10 2 4 3 5 10 2 18 9 7 2 2 1 3 12 1 8 6 2 2
00 4 01 02 03 04
02 1 05
04 2 06 07
03 3 11 12 13
06 1 09
07 2 08 10
16 1 15
13 3 14 16 17
17 2 18 19

Sample Output:

10 5 2 7
10 4 10
10 3 3 6 2
10 3 3 6 2

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int N;//节点数量
int M;//非叶节点数量
int S;//所得权重

struct Node {//孩子表示法
	int weight;
	vector child;
}nodes[110];//下标表示节点编号

//int path[110];//记录路径
vector<vector > path;
vector temp;

void DFS(int index, int len, int sum) {//index当前访问节点，len当前路径长，sum当前路径权重
	temp.push_back(index);
	sum += nodes[index].weight;
	len++;
	if (sum > S)return;//加上次节点后大于S，此路不通
	if (sum == S) {
		if (nodes[temp[len - 1]].child.empty() != 1)return;//有叶节点但sum==S，则表示此路不通
		path.push_back(temp);
		return;
	}
	if (sum < S) {
		for (int i = 0; i < nodes[temp[len - 1]].child.size(); i++) {
			DFS(nodes[temp[len - 1]].child[i], len, sum);
			temp.pop_back();
		}
	}

}

bool cmp(vector a, vector b) {
	int len_a = a.size();
	int len_b = b.size();
	int index = 0;
	while (index < len_a && index < len_b) { if (nodes[a[index]].weight != nodes[b[index]].weight) return nodes[a[index]].weight > nodes[b[index]].weight;
		index++;
	}
	return len_a > len_b;
}

int main() {
	cin >> N;
	cin >> M;
	cin >> S;
	for (int i = 0; i < N; i++) { cin >> nodes[i].weight;
	}
	int non_leaf;
	int child_num;
	int child;
	for (int i = 1; i <= M; i++) { cin >> non_leaf;
		cin >> child_num;
		for (int j = 0; j < child_num; j++) { cin >> child;
			nodes[non_leaf].child.push_back(child);
		}
		//sort(nodes[non_leaf].child.begin(), nodes[non_leaf].child.end(), cmp);
	}
	
	DFS(0, 0, 0);
	sort(path.begin(), path.end(), cmp);
	for (int i = 0; i < path.size(); i++) {
		for (int j = 0; j < path[i].size(); j++) {
			cout << nodes[path[i][j]].weight;
			if (j < path[i].size() - 1)cout << ' ';
			else cout << endl;
	    }
	}
}