边权转点权+差分约束
显然图中不在 \(1\) 到 \(n\) 路径上的边是不会影响答案的，所以现在只考虑 \(1\) 到 \(n\) 路径上的边。
然后就有重要性质，图中 \(1\) 到 \(n\) 的所有路径的航程相同可以转化为，对于每个在 \(1\) 到 \(n\) 某条路径上的 \(u\)，都有 \(1\) 到 \(u\) 的所有路径总长度都相等，证明也显然，反证法即可。
边权转点权：那么说明每个 \(1\) 到 \(u\) 的路径长度 \(d_u\) 是一个定值，也就转化为给每个 \(d_u\) 赋值，满足条件 \(1\le d_v-d_u\le 2\)。
有两个不等式，写成 \(d_u\le d_v-1\) 和 \(d_v\le d_u+2\)，差分约束的形式，建图跑最短路即可。
无解就是有负环。复杂度 \(O(n^2)\)。
#include <iostream>
#include <vector>
#include <cstdio>
#include <cmath>
#include <string>
#include <array>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <bitset>
#define pii std::pair<int, int>
#define fi first
#define se second
#define pb push_back
// 1 <= d[v] - d[u] <= 2
// d[u] <= d[v] - 1 and d[v] <= d[u] + 2
typedef long long i64;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 1e3 + 10, M = 5e3 + 10;
int n, m, cnt;
int vis[N], ins[N];
struct node {
int u, v;
} a[M];
std::vector<int> E[N];
void dfs(int u) {
vis[u] = 1;
for(auto v : E[u]) {
if(!vis[v]) dfs(v);
if(ins[v]) ins[u] = 1;
}
}
struct edge {
int to, nxt, w;
} e[M << 1];
int h[N], dis[N], inq[N], mk[M];
void add(int u, int v, int w) {
e[++cnt].to = v;
e[cnt].nxt = h[u];
e[cnt].w = w;
h[u] = cnt;
}
int tot[N];
bool spfa(int s) {
std::queue<int> q;
for(int i = 1; i <= n; i++) dis[i] = 0x3f3f3f3f;
inq[s] = 1;
dis[s] = 0;
q.push(s);
while(!q.empty()) {
int u = q.front();
q.pop();
inq[u] = 0;
for(int i = h[u]; i; i = e[i].nxt) {
int v = e[i].to;
if(dis[v] > dis[u] + e[i].w) {
dis[v] = dis[u] + e[i].w;
if(!inq[v]) {
inq[v] = 1;
q.push(v);
tot[v]++;
if(tot[v] > n) return 1;
}
}
}
}
return 0;
}
void Solve() {
std::cin >> n >> m;
for(int i = 1; i <= m; i++) {
std::cin >> a[i].u >> a[i].v;
E[a[i].u].pb(a[i].v);
}
ins[n] = 1;
dfs(1);
for(int i = 1; i <= m; i++) {
if(ins[a[i].u] && ins[a[i].v]) {
add(a[i].v, a[i].u, -1);
add(a[i].u, a[i].v, 2);
mk[i] = 1;
}
}
if(spfa(1)) {
std::cout << "No\n";
return;
}
std::cout << "Yes\n";
for(int i = 1; i <= m; i++) {
if(!mk[i]) std::cout << "1\n";
else {
std::cout << dis[a[i].v] - dis[a[i].u] << "\n";
}
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
Solve();
return 0;
}