/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return reverseList(nullptr, head);
    }
    // tail是head的前一个节点,反转head
    // 最后返回反转后的头指针
    ListNode* reverseList(ListNode* tail, ListNode* head){
        if(!head) return tail;
        ListNode* next = head->next;	// 记录head的下一个节点
        head->next = tail;				// head 指向tail
        tail = head;					// tail 作为head继续递归
        return reverseList(tail, next);
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head){
        if(!head) return head;
        ListNode* pre = nullptr;        // 初始时head的前一个节点为空
        ListNode* mid = head;
        while(mid&&mid->next){
            ListNode* tail = mid->next;     // 记录mid的下一个节点
            mid->next = pre;
            pre = mid;
            mid = tail;
        }
        mid->next = pre;				// pre始终是mid的前一个节点,循环结束后mid指向pre
        return mid;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution
{
public:
    bool isPalindrome(ListNode *head)
    {
        if (!head || !head->next)
            return true;
        ListNode *tail = head->next;
        ListNode *mid = head;
        bool odd = false;		// odd 判断链表长度是否为奇数
        while (tail && tail->next)
        {
            tail = tail->next;
            mid = mid->next;
            if (tail && tail->next)
            {
                tail = tail->next;
                odd = false;		// tail一次能走两步,是偶数长度的链表
            }
            else
            {
                odd = true;			// 链表这一次走一步就到了尾部,是奇数长度的链表
                break;
            }
        }
        ListNode *right = mid->next;	// 记录mid中间节点的下一个节点
        ListNode *left = reverse(head, mid);

        if (odd)
            left = left->next;			// 如果是奇数链表,左边链表左边走一位
		
        // 中间到两边开始判断,是否为回文链表
        while (right && left)
        {

            if (right->val != left->val)
                return false;

            right = right->next;
            left = left->next;
            if (!left && !right)
                break;
        }
        return true;
    }

    // 反转head到tail部分的链表
    ListNode *reverse(ListNode *head, ListNode *till)
    {
        if (!head || !head->next)
            return head;
        ListNode *pre = nullptr;
        ListNode *mid = head;
        while (mid != till && mid->next)
        {
            ListNode *tail = mid->next;
            mid->next = pre;
            pre = mid;
            mid = tail;
        }
        mid->next = pre;
        return mid;
    }
};

int partition(vector<int> nums, int left, int right){
	int base = nums[left];
	while(left<right){
		while(left<right&&nums[right]>base)
			right--;
		nums[left] = nums[right];
		while(left<right && nums[left]<=base)
			++left;
		nums[right] = nums[left];
	}
	nums[left] = base;
	return left;
}

void quickSort(vector<int> nums,const int left, const int right){
	if(left<right){
		int index = partition(nums, left, right);
		quickSort(nums, left, index);
		quickSort(nums, index+1, right);
	}
}

typedef long long LL;

LL mergeSort(VI& nums, const int low, const int high) {
	LL ans = 0;
	if (high <= low)
		return 0;
	else if (high - low == 1) {
		if (nums[low] > nums[high]) {
			swap(nums[low], nums[high]);
			ans++;
		}
		return ans;
	}
	int mid = low + (high - low) / 2;
	LL left = mergeSort(nums, low, mid);
	LL right = mergeSort(nums, mid + 1, high);
	ans = left + right;
	
	VI leftNums(nums.begin() + low, nums.begin() + mid + 1);
	VI rightNums(nums.begin() + mid + 1, nums.begin() + high + 1);
	int i = 0, j = 0, index = low;
	while (i < leftNums.size() && j < rightNums.size()) {
		if (leftNums[i] <= rightNums[j])
			nums[index++] = leftNums[i++];
		else {
			nums[index++] = rightNums[j++];
			ans += leftNums.size() - i;
		}
	}
	while (i < leftNums.size())
		nums[index++] = leftNums[i++];
	while (j < rightNums.size())
		nums[index++] = rightNums[j++];
	return ans;
}

int64_t reverseNum(vector<int> nums, int low, int high){
	uint64_t ans = 0;
	if(low>=high)
		return ans;
	else if(high - low == 1){
		if(nums[low]>nums[high]){
			swap(nums[low], nums[high]);
			++ans;
		}
		return ans;
	}
	int mid = low + (high-low)/2;
	int64_t left = reverseNum(nums, low, mid);
	int64_t right = reverseNum(nums, mid+1, high);
	ans += left + right;
	vector<int> leftNums(nums.begin()+low, nums.begin()+mid+1);
	vector<int> rightNums(nums.begin()+mid+1, nums.begin()+high+1);
	int i = 0, j = 0, index = low;
	
	while( i<leftNums.size() && j< rightNums.size() ){
		if(leftNums[i]<=rightNums[j])
			nums[index++] = leftNums[i++];
		else{
			nums[index++] = rightNums[j++];
			ans += leftNums.size()-i;	// 
		}
	}
	while(i<leftNums.size())
		nums[index++] = leftNums[i++];
	while(j<rightNums.size())
		nums[index++] = rightNums[j++];
	return ans;
}

double minDistance(vector<Point>& points, CI low, CI high) {
	if (low >= high)
		return 0;
	else if (low == high - 1) {
		double dis = distance(points[low], points[high]);
		if (points[low].y > points[high].y)
			swap(points[low], points[high]);
		return dis;
	}

	int mid = low + (high - low) / 2;
	int middle = points[mid].x;
	double left = minDistance(points, low, mid);
	double right = minDistance(points, mid, high);
	double ans = min(left, right);
	auto f = [](const Point& p1, const Point& p2)->bool {return p1.y < p2.y; };
	sort(points.begin() + low, points.begin() + high + 1, f);
	vector<Point> tmp;
	for (int i = low; i < high; ++i) {
		if (abs(points[i].x - middle) <= ans)
			tmp.emplace_back(points[i]);
	}

	for (int i = 0; i < tmp.size(); ++i) {
		for (int j = i + 1; j < min(static_cast<int>(tmp.size()), i + 12); ++j)
			ans = min(ans, distance(tmp[i], tmp[j]));
	}
	return ans;
}

class UnionFind{
public:
    vector<int> sz; // 表示每个集合的大小
    vector<int> parent; // 表示每个顶点最终的父节点
                        // 初始化每个顶点父节点是其自身
    int cnt;
    UnionFind(const int n){
        sz.assign(n, 1);
        cnt = n;
        parent.resize(n, 0);
        for(int i = 0; i < n; ++i)
            parent[i] = i;
    }

    // 找某个节点的父亲节点,注意返回值不能是 bool类型，必须是整数类型
    int find(const int x){
        if(x!=parent[x])
            parent[x] = find(parent[x]);
        return parent[x];
    }

    // 合并两个节点
    bool merge(const int x, const int y){
        int px = find(x);
        int py = find(y);
        if(px==py)  return false;
        if(sz[px]>=sz[py]){
            sz[px]+=sz[py];
            parent[py] = px;
        }
        else{
            sz[py]+=sz[px];
            parent[px] = py;
        }
        --cnt;
        return true;
    }
    int getCnt(){return cnt;}
};

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<double> VD;
typedef vector<VD> VVD;

// 边的定义
struct Edge {
	int from, to;
	double dis;
	Edge(CI f, CI t, CD d) :from(f), to(t), dis(d) {};
	bool operator < (const Edge& e)const { return this->dis > e.dis; };
};

// 图用邻接矩阵存储的Prime算法
double MST(const VVD& graph) {
	double ans = 0;
	VI visit(graph.size(), 0);
	priority_queue<Edge> myQueue;
	for (int i = 0; i < graph.size(); ++i) {
		myQueue.emplace(0, i, graph[0][i]);
	}
	VD dis(graph[0]);
	while (!myQueue.empty()) {
		Edge e = myQueue.top();
		myQueue.pop();
		if (visit[e.to] == 1)
			continue;
		visit[e.to] = 1;
		ans += e.dis;
		dis[e.to] = e.dis;
		for (int i = 0; i < graph.size(); ++i)
			if (visit[i] == 0 && graph[e.to][i] < dis[i])
				myQueue.emplace(e.to, i, graph[e.to][i]);
	}
	return ans;
}

// 边的定义
struct Edge {
	int from, to;
	double dis;
	Edge(CI f, CI t, CD d) :from(f), to(t), dis(d) {};
	bool operator < (const Edge& e)const { return this->dis < e.dis; };
};

// kruskal算法,需要用到并查集
double MST(const vector<Edge> edgeVec,const int vertex) {
	sort(edgeVec.begin(), edgeVec.end());

    QuickUnion qu(vertex);
    double ans = 0;
    int edgCnt = 0;
    for(auto&e :edgeVec){
        if(qu.merge(e.from, e.to)){
            ans += e.dis;
            edgCnt++;
            if(edgCnt==vertex-1)
                break;
        }
    }
    return ans;
}

typedef vector<int> VI;
typedef vector<VI> VVI;

// 边的定义
struct Edge {
	int from, to;
	int dis;
	Edge(CI f, CI t, CD d) :from(f), to(t), dis(d) {};
	bool operator < (const Edge& e)const { return this->dis > e.dis; };
};

// 图用邻接矩阵存储的, 优先级队列实现,,计算start到target的最近距离
int dijkstra(const VVI& graph, const int start, const int target) {
	VI dis(graph.size(), INT_MAX);
	dis[start] = 0;
	VI visit(graph.size(), 0);
	priority_queue<Edge> myQueue;
	myQueue.emplace(start, start, 0);
	while(!myQueue.empty()){
		Edge e = myQueue.top();
		myQueue.pop();
		if(visit[e.to]==1)
			continue;
		visit[e.to] = 1;
		dis[e.to]= e.dis;
		for(int i = 0;i<graph.size();++i){
			if( visit[i]==0 && dis[i]- graph[e.to][i]> dis[e.to])
				myQueue.emplace(e.to, i, dis[e.to]+ graph[e.to][i])
		}
	}
	return dis[target];
}

typedef vector<int> VI;
typedef vector<VI> VVI;

// 图用邻接矩阵存储, 队列实现的spfa算法,计算start到target的最近距离
int spfa(const VVI& graph, const int start, const int target) {
	vector<int> dis(graph.size(), INT_MAX);
	dis[start] = 0;
	queue<int> myQueue;
	VI enqueue(graph.size(), 0);
	myQueue.push(start);
	enqueue[start] = 1;
	while(!myQueue.empty()){
		int topNode = myQueue.front();
		myQueue.pop();
		enqueue[topNode] = 0;
		for(int i = 0;i<graph.size();++i){
			if(dis[i]- graph[topNode][i]> dis[topNode]){
				dis[i] = dis[topNode]+graph[topNode][i];
				if(enqueue[i]==0){
					myQueue.emplace(i);
					enqueue[i] = 1;
				}
			}
		}
	}
	return dis[target];
}

#include <vector>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <climits>
#include <string>
#include <algorithm>

using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef const int CI;

int solution(const VI& nums, CI K) {
	VVI F(K + 1, VI(nums.size(), 0));
	for (int k = 1; k <= K; ++k) {
		int tmp = F[k - 1][0] - nums[0];
		for (int i = 1; i < nums.size(); ++i) {
			tmp = max(F[k-1][i] - nums[i], tmp);
			F[k][i] = max(F[k][i - 1], nums[i] + tmp);
		}
	}
	return F[K][nums.size() - 1];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int castCount; cin >> castCount;
	while (castCount--) {
		int N;
		cin >> N;
		VI nums(N, 0);
		for (auto&e : nums)
			cin >> e;
		int ans = solution(nums,2);
		cout << ans << endl;
	}
	return 0;
}

/*
* Dinic algo for max flow
*
* This implementation assumes that #nodes, #edges, and capacity on each edge <= INT_MAX,
* which means INT_MAX is the best approximation of INF on edge capacity.
* The total amount of max flow computed can be up to LLONG_MAX (not defined in this file),
* but each 'dfs' call in 'dinic' can return <= INT_MAX flow value.
*/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>
#include <assert.h>
#include <queue>
#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>

#define N (1000+2)
#define M (2*N*N+4*N)

using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef const int CI;

struct edge {
	int v, cap, next;
};
edge e[M];

int head[N], level[N], cur[N];
int num_of_edges;

/*
* When there are multiple test sets, you need to re-initialize before each
*/
void dinic_init(void) {
	num_of_edges = 0;
	memset(head, -1, sizeof(head));
	return;
}

int add_edge(int u, int v, int c1, int c2) {
	int& i = num_of_edges;

	assert(c1 >= 0 && c2 >= 0 && c1 + c2 >= 0); // check for possibility of overflow
	e[i].v = v;
	e[i].cap = c1;
	e[i].next = head[u];
	head[u] = i++;

	e[i].v = u;
	e[i].cap = c2;
	e[i].next = head[v];
	head[v] = i++;
	return i;
}

void print_graph(int n) {
	for (int u = 0; u < n; u++) {
		printf("%d: ", u);
		for (int i = head[u]; i >= 0; i = e[i].next) {
			printf("%d(%d)", e[i].v, e[i].cap);
		}
		printf("\n");
	}
	return;
}

/*
* Find all augmentation paths in the current level graph
* This is the recursive version
*/
int dfs(int u, int t, int bn) {
	if (u == t) return bn;
	int left = bn;
	for (int &i = cur[u]; i >= 0; i = e[i].next) {
		int v = e[i].v;
		int c = e[i].cap;
		if (c > 0 && level[u] + 1 == level[v]) {
			int flow = dfs(v, t, min(left, c));
			if (flow > 0) {
				e[i].cap -= flow;
				e[i ^ 1].cap += flow;
				cur[u] = i;
				left -= flow;
				if (!left) break;
			}
		}
	}
	if (left > 0) level[u] = 0;
	return bn - left;
}

bool bfs(int s, int t) {
	memset(level, 0, sizeof(level));
	level[s] = 1;
	queue<int> q;
	q.push(s);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		if (u == t) return true;
		for (int i = head[u]; i >= 0; i = e[i].next) {
			int v = e[i].v;
			if (!level[v] && e[i].cap > 0) {
				level[v] = level[u] + 1;
				q.push(v);
			}
		}
	}
	return false;
}

LL dinic(int s, int t) {
	LL max_flow = 0;

	while (bfs(s, t)) {
		memcpy(cur, head, sizeof(head));
		max_flow += dfs(s, t, INT_MAX);
	}
	return max_flow;
}

int upstream(int s, int n) {
	int cnt = 0;
	vector<bool> visited(n);
	queue<int> q;
	visited[s] = true;
	q.push(s);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = head[u]; i >= 0; i = e[i].next) {
			int v = e[i].v;
			if (e[i].cap > 0 && !visited[v]) {
				visited[v] = true;
				q.push(v);
				cnt++;
			}
		}
	}
	return cnt; // excluding s
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int m, n;
	cin >> m >> n;
	int s = 0, t = 2 * n + 1;
	dinic_init();
	for (int i = 0; i < m; ++i) {
		int a, b; cin >> a >> b;
		add_edge(a, b + n, 1, 0);
	}
	for (int i = 0; i < n; ++i) {
		add_edge(s, i + 1, 1, 0);
		add_edge(i + n + 1, t, 1, 0);
	}
	LL maxFlow = dinic(s, t);
	printf("%lld\n",n - maxFlow);
}
// 参考：https://blog.csdn.net/pengwill97/article/details/82765383

#include <vector>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <climits>
#include <queue>
#include <cstdio>

using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef const int CI;

struct Gift {
	int level;
	int value;
	Gift(int l = 0, int v = 0) :level(l), value(v) {};
};

struct Edge {
	int from, to;
	int dis;
	Edge(int f, int t, int d) :from(f), to(t), dis(d) {}
	bool operator<(const Edge& e)const { return this->dis > e.dis; };
};

// dijkstra 算法，low和high分别表示等级范围
int solution(const VVI& graph, const vector<Gift>& gift, CI low, CI high) {
	VI dis(graph.size(), INT_MAX);
	dis[0] = 0;
	priority_queue<Edge> myQueue;
    // 每次加入边的时候考虑等级差距
	for (int i = 1; i < graph.size(); ++i){
		if (gift[i].level >= low&&gift[i].level <= high)
			dis[i] = graph[0][i];
		else
			dis[i] = INT_MAX;
		myQueue.push(Edge(0, i, dis[i]));
	}
	VI visit(graph.size(), 0);
	visit[0] = 1;
	while (!myQueue.empty()) {
		Edge e = myQueue.top();
		myQueue.pop();
		if (visit[e.to] == 1)
			continue;
		visit[e.to] = 1;
		dis[e.to] = e.dis;
		for (int j = 1; j < graph.size(); ++j) {
            // 每次加入边的时候考虑等级差距
			if (visit[j] == 0 && gift[j].level >= low&&gift[j].level <= high&&dis[e.to] < dis[j] - graph[e.to][j])
				myQueue.push(Edge(e.to, j, dis[e.to] + graph[e.to][j]));
		}
	}
	return dis[1];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int M, N;
	while (cin >> M >> N) {
		vector<Gift> gift(N + 1);
		
		VVI graph(N + 1, VI(N + 1, INT_MAX));
		for (int i = 0; i < N + 1; ++i)
			graph[i][i] = 0;
		
		for (int i = 1; i <= N; ++i) {
			int alter;
			cin >> gift[i].value >> gift[i].level >> alter;
			graph[0][i] = gift[i].value;
			for (int j = 0; j < alter; ++j) {
				int x, y;
				cin >> x >> y;
				graph[x][i] = y;
			}
		}
		CI L = gift[1].level;
		int ans = INT_MAX;
		for (int i = 0; i <= M; ++i) {
			int tmp = solution(graph, gift,  L - i, L - i + M);
			ans = min(ans, tmp);
		}
		printf("%d\n", ans);
	}
	return 0;
}

scanf("%d%d%d",&x, &y, &w);
graph[x][y] = w;
graph[y][x] = w;

scanf("%d%d%d",&x, &y, &w);
graph[x][y] = min(graph[x][y],w);
graph[y][x] = min(graph[y][x], w);

#include<vector>
#include<cstdio>
#include<queue>
#include<queue>
#include<functional>
using namespace std;

// 表示边的结构体
struct Edge {
	int from, to, distance;
	Edge(int f, int t, int d) :from(f), to(t), distance(d) {};
	bool operator <(const Edge& e)const { return this->distance > e.distance; };
};

// 计算从source出发，到图中每个顶点的最短距离
void dijkstra(const vector<vector<int>>& graph, const int source, vector<int>& distance) {
	vector<int> visit(graph.size(), 0);
	priority_queue<Edge> myQueue;
	visit[0] = 1;
	visit[source] = 1;
	for (int i = 1; i < graph.size(); ++i)
		if(visit[i]==0)
			myQueue.emplace(source, i, distance[i]);
	
	while (!myQueue.empty()) {
		Edge e = myQueue.top();
		myQueue.pop();
		if (visit[e.to] == 1)
			continue;
		visit[e.to] = 1;
		distance[e.to] = e.distance;
		for (int j = 1; j < graph.size(); ++j) {
			if (visit[j] == 0 && distance[e.to] + graph[e.to][j] < distance[j]){
				myQueue.emplace(e.to, j, distance[e.to] + graph[e.to][j]);
			}
		}
	}
}


int main() {
	int F, P, C, M;
	while (scanf("%d%d%d%d", &F, &P, &C, &M) != EOF) {
		vector<vector<int>> graph(F + 1, vector<int>(F + 1, static_cast<int>(1e9)));
		for (int i = 0; i < graph.size(); ++i)
			graph[i][i] = 0;
		for (int i = 0; i < P; ++i) {
			int x, y, w;
			scanf("%d%d%d",&x, &y, &w);
			graph[x][y] = min(graph[x][y],w);
			graph[y][x] = min(graph[y][x], w);
		}
		vector<int> cows(C, 0);
		for (int j = 0; j < C; ++j)
			scanf("%d",&cows[j]);
		vector<int> distance(graph[1]);
		dijkstra(graph, 1,distance);
		int ans = 0;
		for (int i = 0; i < cows.size(); ++i)
			if (distance[cows[i]] <= M)
				++ans;
		printf("%d\n",ans);
		for (int i = 0; i < cows.size(); ++i)
			if (distance[cows[i]] <= M)
				printf("%d\n",i+1);
	}
	return 0;
}