#include <stdio.h>

#include <string.h>

#include <iostream>

using namespace std;

const int N = 550;

int match[N], g[N][N], vis[N], link[N];

int n, m, e, tag, ans = 0;

bool dfs(int u) {

	for(int v=1; v<=m; ++v) {

		if(!g[u][v] or vis[v] == tag) continue;

		vis[v] = tag;

		if(!match[v] or dfs(match[v])) {

			match[v] = u;

			return true;

		}

	}

	return false;

}

int main() {

	scanf("%d%d%d", &n, &m, &e);

	for(int i=1, u, v; i<=e; ++i) {

		scanf("%d%d", &u, &v);

		g[u][v] = true;

	}

	for(int i=1; i<=n; ++i) {

		tag = i;

		if(dfs(i)) ++ans;

	}

	printf("%d\n", ans);

	for(int i=1; i<=m; ++i) link[match[i]] = i;

	for(int i=1; i<=n; ++i) printf("%d ", link[i]);

	return 0;

}

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <queue>

using namespace std;

const int N = 550;

int fa[N], match[N], pre[N], vis[N];

int tag = 0, n, m, ans = 0;

int flag[N];

bool g[N][N];

queue<int> q;

void clear(queue<int> &q) {

	queue<int> empty;

	swap(q, empty);

}

int belong(int u) {

	return fa[u] == u ? u : fa[u] = belong(fa[u]);

}

void path(int u) {

	while(u) {

		int v = match[pre[u]];

		match[u] = pre[u];

		match[pre[u]] = u;

		u = v;

	}

}

int lca(int u, int v) {

	++tag;

	u = belong(u);

	v = belong(v);

	while(vis[u] != tag) {

		vis[u] = tag;

		u = belong(pre[match[u]]);

		if(v) swap(u, v);

	}

	return u;

}

void connect(int u, int v, int root) {

	while(belong(u) != root) {

		pre[u] = v;

		v = match[u];

		if(flag[v] == 2) {

			q.push(v);

			flag[v] = 1;

		}

		if(belong(u) == u) fa[u] = root;

		if(belong(v) == v) fa[v] = root;

		u = pre[v];

	}

}

bool bfs(int u) {

	memset(flag, 0, sizeof flag);

	memset(pre, 0, sizeof pre);

	for(int i=1; i<=n; ++i) fa[i] = i;

	clear(q);

	q.push(u);

	flag[u] = 1;

	while(!q.empty()) {

		u = q.front();

		q.pop();

		for(int v=1; v<=n; ++v) {

			if(!g[u][v]) continue;

			if(flag[v] == 0) {

				pre[v] = u;

				if(match[v] == 0) {

					path(v);

					return true;

				}

				q.push(match[v]);

				flag[v] = 2;

				flag[match[v]] = 1;

			} else {

				if(flag[v] == 2) continue;

				if(belong(u) == belong(v)) continue;

				int root = lca(u, v);

				connect(u, v, root);

				connect(v, u, root);

			}

		}

	}

	return false;

}

int main() {

	scanf("%d%d", &n, &m);

	for(int i=1, u, v; i<=m; ++i) {

		scanf("%d%d", &u, &v);

		g[u][v] = g[v][u] = true;

	}

	for(int i=1; i<=n; ++i) 

		if(match[i] == 0 and bfs(i)) ++ans;

	printf("%d\n", ans);

	for(int i=1; i<=n; ++i) printf("%d ", match[i]);

	return 0;

}

#include <stdio.h>

#include <string.h>

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 440;

const LL INF = 0x3f3f3f3f3f3f3f3f;

bool vis[N];

int pre[N], link[N], res[N];

int n, m, e;

LL g[N][N], lx[N], ly[N], d[N], ans = 0;

void bfs(int k) {

	int x, y = 0;

	LL min1 = INF, delta;

	memset(vis, false, sizeof vis);

	memset(pre, 0, sizeof pre);

	memset(d, 0x3f, sizeof d);

	link[y] = k;

	do {

		x = link[y], delta = INF, vis[y] = true;

		for(int i=1; i<=m; ++i) {

			if(!vis[i]) {

				if(d[i] > lx[x] + ly[i] - g[x][i]) {

					d[i] = lx[x] + ly[i] - g[x][i];

					pre[i] = y;

				}

				if(delta > d[i]) delta = d[i], min1 = i;

            }

        }

        for(int i=0; i<=m; ++i)

        	if(vis[i]) lx[link[i]] -= delta, ly[i] += delta;

        	else d[i] -= delta;

        y = min1;

    } while(link[y]);

    while(y) link[y] = link[pre[y]], y = pre[y];

}

int main() {

	scanf("%d%d%d", &n, &m, &e);

	m = max(n, m);

	for(int i=1; i<=e; ++i) {

		int u, v; LL w;

		scanf("%d%d%lld", &u, &v, &w);

		g[u][v] = w;

		lx[u] = max(lx[u], w);

	}

	for(int i=1; i<=n; ++i) bfs(i);

	for(int i=1; i<=m; ++i) {

		if(!g[link[i]][i]) continue;

		ans += g[link[i]][i];

		res[link[i]] = i;

	}

	printf("%lld\n", ans);

	for(int i=1; i<=n; ++i) printf("%d ", res[i]);

	return 0;

}