By 2000, a drawing started appearing in pamphlets and newspapers (second pic) of a moustachioed man in a turtleneck sweater. Then the army captured a group photo in 2001 with a bearded Prachanda (third pic).
The chairman had named Nepal's brand of Maoism after himself: Marxism-Leninism-Maoism-Prachanda Path. This played on the word 'path', meaning 'way' in both English and Sanskrit. But more importantly, it had resonance with the 'Shining Path' of the senderistas in Peru.
As far back as 1993, the writing was?quite literally?on the wall. Trekkers hiking in the mountains would find red grafitti scrawled on boulders: "Release Comrade Gonzalo." The revolution had leapfrogged from the Andes to the Himalaya.
In an interview with Revolutionary Worker in 2000, Prachanda gave a hint of what was to come: 'Right now, subjectively, the proletarian forces are weak, after Mao's death and the counter-revolution in China. Nepal is a small country, we are a small party, but we have a big perspective. Our People's War may be a spark, but a spark for a prairie fire...the People's War in Nepal is contributing to making and accelerating this new wave of revolution. And Maoism should be the commander of this new wave of world revolution.'
Prachanda has given many interviews since then, and in these has contradicted himself many times, or at least tried to rationalise. Eight years ago, Prachanda sounded vehement: 'I hate revisionism. I seriously hate revisionism. I never compromise with revisionism. I fought and fought again with revisionism. And the party's correct line is based on the process of fighting revisionism.'
Today, Indian Naxalites and international revolutionaries accuse Prachanda himself of revisionism. The chairman has explained that the party's ideological brainstorming in 2005 concluded that due to the domestic and international geopolitical situation, military state capture was untenable. Therefore, the party had analysed where socialism had gone astray in other countries, why the revolution had failed to deliver: because of the absence of multi-party competition.
In other words, comrades elsewhere had taken the 'dictatorship of the proletariat' to mean dictatorship in governance. Nepali Maoists, he said, were different.
Now in a position of power, Dahal has already been forced to be more responsible in his comments. The man who used to denounce "American imperialism and Indian expansionism" and accuse those countries of trying to assassinate him, now meets the ambassadors of both countries and assures them of his party's adherence to multi-party democracy, the free market and support for foreign investment.
He also has to answer a lot of people from the moderate left parties who are asking: if you were for private property and the free market all along, why did you wage war and kill all those people?
Dahal was born in a poor bahun family from Tanahu which, like tens of thousands of others, was resettled in the cleared jungles of Chitwan after the eradication of malaria in the 1960s. His father was a frontiersman, farming and raising a family at the edge of the jungle. Life was hard in the mountains, but it wasn't easy in the plains either. It was a struggle to survive?against wild animals, ruthless moneylenders and a government which abandoned resettled farmers to fend for themselves.
In college, Dahal was strongly influenced by communist ideology. He had seen Nepal's yawning economic gulf at first hand while growing up in Chitwan. "I never really understood why we had to struggle so hard to survive from day to day while our neighbours had all the luxuries," Dahal once told an interviewer.
In 1980, at the age of 25, Prachanda became a member of the Communist Party, which was in the throes of a split, reflecting fissures in the international communist movement itself. Prachanda came into contact with Nepal's senior communists, who made a strong impression on him but with whom he later disagreed about the relevance and need for waging armed struggle.
Prachanda enrolled at the Agriculture Campus in Rampur, Chitwan, which was set up with American aid and had become a hotbed of student politics. After graduation in 1976 he spent two years in a teaching job in Gorkha's Arughat.
A faded photograph (first pic) from the period shows Prachanda sitting on a boulder with two of his colleagues, dressed in a black jacket with a stern expression on his face. Even then the young Dahal seemed to know he was headed for greater things. He had a passion for Hindi movies, listened avidly to songs on the radio and was a keen dancer, but he also kept a stack of books by Marx, Lenin and Mao under his bed.
A fellow teacher in Arughat told Nepali Times Dahal had once said to him: "If I want to be minister, I can easily achieve that."
]After his teaching job, Dahal did a brief stint working for the US-funded Rapti Project. Dahal remembers thinking just how wasteful foreign aid was, and also noted the segregation between Nepalis and Americans in the project office. He says he saw how little of the aid money actually went to improving people's lives, and even the little that did just made the people more dependent. By the mid-1990s Salyan, Rolpa, Jajarkot and Pyuthan were as underdeveloped as ever; only the rusting hulks of American jeeps remained.
Unlike other communist leaders, Dahal stayed underground even after the ban on political parties was lifted in 1990. While his comrade-in-arms Baburam Bhattarai engaged in open politics with the United People's Front, Dahal was working behind the scenes to prepare for armed struggle with his trusted comrade Mohan Baidya. The strategy and tactics were straight out of Mao's red book. When the war started in 1996 it spread rapidly, not because the Maoists were exceptionally brilliant or militarily strong, but because the state was so brutal, factionalised and corrupt.
For Prachanda, like all revolutionaries, the end justified the means. He said: "In a revolution, we had to weaken the repressive state, and any institution or structure that represented the government was a legitimate target."
Many committed social workers, popular teachers and enlightened farmers were killed by his cadre. Most were tortured in front of the entire village or their families in an effective use of terror. When asked about this in a meeting with editors recently, Dahal said: "I never ordered our forces to torture anyone. If anyone had to be exterminated, I told them they should do it quickly, with a bullet to the temple."
He says this in his party office where the portraits of Marx, Engels, Lenin, Stalin and Mao hang above his head. "Why Stalin?" we ask him. "Stalin made mistakes, but he was a great revolutionary and he defeated fascism," Dahal explained.
Prachanda's transformation into Pushpa Kamal Dahal started during the election campaign this year. In speech after speech, he glossed over his party's brutal past. He tried to force people to look to the future and championed the cause of the poor and oppressed. In a country where 95 per cent of the people are poor, this was a failsafe strategy.
Dahal was more surprised about his party's victory than anyone else. He was so unsure about his own win that he tried to negotiate with the other parties a guaranteed win for himself and his senior leaders.
Dahal had not just underestimated the people's desire for change, but also their tolerance and forgiving nature. Through the vote, the people were telling Prachanda: don't you dare take us back to war.
But there are detractors, even within his party, who say Dahal has gone soft. After decades of being underground, the father of three likes the finer things in life, dresses well and can't resist good food. Public expectations are very high, and his party will have to start delivering on his promise to turn Nepal into the 'Switzerland of Asia'.
Dahal may find that waging war was the easy part. Now that he may be heading the government that he fought to overthrow, he must be wondering how to start rebuilding a country destroyed by a war he started.
Dahal will be tempted to achieve all this with unsustainably populist economic measures, or by clamping down and asserting the authoritarianism that he is familiar with. The real battle of Dahal's life is just beginning: how he can lead a party in power to deliver the goods. This is what he will be judged by in history.
Reporting by Sheere Ng in Gorkha